package stack;

import org.w3c.dom.Node;

/**
 * 用单向链表实现栈
 */
public class SingleLinkedListStackDemo {
    public static void main(String[] args) {
        /*SingleLinkedListStack singleLinkedListStack = new SingleLinkedListStack(5);
        singleLinkedListStack.push("1");
        singleLinkedListStack.push("2");
        singleLinkedListStack.push("3");
        singleLinkedListStack.push("4");
        singleLinkedListStack.push("5");
        singleLinkedListStack.push("6");
        singleLinkedListStack.list();
        singleLinkedListStack.pop();
        System.out.println("chuzhan");
        singleLinkedListStack.list();*/
        SingleLinkedListStack2 singleLinkedListStack2 = new SingleLinkedListStack2(5);
        singleLinkedListStack2.push("1");
        singleLinkedListStack2.push("2");
        singleLinkedListStack2.push("3");
        singleLinkedListStack2.list();
        singleLinkedListStack2.pop();
        System.out.println(111);
        singleLinkedListStack2.list();
        singleLinkedListStack2.push("3");
        singleLinkedListStack2.list();

    }
}

class SingleLinkedListStack {
    private StackNode head = new StackNode(0,"");
    private int size;
    private int top = -1;//栈顶元素

    public SingleLinkedListStack(int size) {
        this.size = size;
        for (int i = 0; i < size; i++) {
            StackNode node = new StackNode(i,"");
            //创建临时节点
            StackNode temp = head;
            while (temp.next != null){
                temp = temp.next;
            }
            temp.next = node;
        }
    }
    public boolean isFull() {
        return top == size - 1;
    }
    public boolean isEmpty() {
        return top == -1;
    }
    public void push(String data){
        if (isFull()){
            System.out.println("栈满");
            return;
        }
        StackNode temp = head;

        top = top+1;
        while (true){
            if(temp.next.no == top){
                //找到存储位置了
                temp.next.data = data;
                break;
            }
            temp = temp.next;
        }

    }

    //出栈
    public String pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空，不能再出栈啦~~");
        }
        StackNode temp = head;
        while (true){
            if(temp.next.no == top){
                //找到存储位置了
                String data = temp.next.data;
                temp.next = null;
                top = top-1;
                return data;
            }
            temp = temp.next;
        }
    }

    //遍历栈
    public void list(){
        if (isEmpty()){
            System.out.println("栈空，没有数据~~");
            return;
        }
        StackNode temp = head;
        while (true){
            if(temp.next == null || temp.no == top){
                break;
            }
            System.out.println(temp.next);
            temp = temp.next;
        }
    }
}
//这个方法是直接让存节点 然后每次添加的节点设置为头节点
class SingleLinkedListStack2{
    private StackNode2 head;
    private int size;//栈的大小
    private int num = 0;//已经存放的数量
    public SingleLinkedListStack2(int size) {
        this.size = size;
    }
    public boolean isFull(){
        return num == size;
    }
    public boolean isEmpty(){
        return num == 0;
    }
    //入栈
    public void push(String data){
        if (isFull()){
            System.out.println("栈满");
            return;
        }
        if (head == null){
            //头结点为空
            head = new StackNode2(data);
            num++;
            return;
        }
        StackNode2 node = new StackNode2(data);
        node.next = head;
        head = node;
        num++;
        System.out.println("入栈成功");
    }

    public String pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空，不能再出栈啦~~");
        }
        String data = head.data;
        head = head.next;
        num--;
        System.out.println("出栈成功");
        return data;
    }
    public void list(){
        if (isEmpty()){
            System.out.println("栈空，没有数据~~");
            return;
        }
        StackNode2 temp = head;
        for (int i = 0; i < num; i++) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

}

class StackNode2{
    public String data;
    public StackNode2 next;
    public StackNode2(String data) {
        this.data = data;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public StackNode2 getNext() {
        return next;
    }

    public void setNext(StackNode2 next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "StackNode2{" +
                "data='" + data + '\'' +
                '}';
    }
}
class StackNode {
    public int no;
    public String data;
    public StackNode next;

    public StackNode(int no,String data) {
        this.no = no;
        this.data = data;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public StackNode getNext() {
        return next;
    }

    public void setNext(StackNode next) {
        this.next = next;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "StackNode{" +
                "no=" + no +
                ", data='" + data + '\'' +
                '}';
    }
}


